

// ffd_binpack_umap.cpp
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <unordered_map>
#include <vector>

constexpr int CAP = 104;

/* ---------- Bin 结构：保存 <idx,val> 对 ------------ */
struct Bin {
    std::vector<std::pair<int, int>> items;  // {idx, val}
    int sum = 0;

    bool try_put(const std::pair<int, int>& it) {
        if (sum + it.second > CAP) return false;
        items.push_back(it);
        sum += it.second;
        return true;
    }
};

/* ---------- FFD 算法（输入为 pair 向量） ----------- */
std::vector<Bin> first_fit_decreasing(std::vector<std::pair<int,int>> sorted_elems) {
    /* 1. 按 value 降序，value 相等时按 idx 升序 */


    /* 2. 依次放入桶 */
    std::vector<Bin> bins;
    for (const auto& it : sorted_elems) {
        bool placed = false;
        for (auto& b : bins) {
            if (b.try_put(it)) {
                placed = true;
                break;
            }
        }
        if (!placed) {                 // 3. 放不下 → 新建桶
            bins.push_back(Bin{{it}, it.second});
        }
    }
    return bins;
}

// int main() {
//     /* -------- 用 unordered_map 录入数据 -------- */
//     std::unordered_map<int,int> umap{
//         {1,102},{2,100},{3,78},{4,34},{5,26},{6,5},
//         {7,68},{8,45},{9,37},{10,18},{11,39},
//         {12,69},{13,90},{14,40},{15,35},{16,67},
//         {17,3},{18,4},{19,55}
//     };

//     /* 把 (idx,val) 搬到 vector 便于排序 */
//     std::vector<std::pair<int,int>> sorted_elems(umap.begin(), umap.end());
//     std::sort(sorted_elems.begin(), sorted_elems.end(),
//               [](const auto& a, const auto& b) {
//                   return (a.second > b.second) ||
//                          (a.second == b.second && a.first < b.first);
//               });

//     /* -------- 运行 FFD 并输出 -------- */
//     auto bins = first_fit_decreasing(sorted_elems);

//     for (std::size_t i = 0; i < bins.size(); ++i) {
//         const auto& b = bins[i];
//         std::cout << "Bin " << (i+1) << ": [";
//         for (std::size_t j = 0; j < b.items.size(); ++j) {
//             const auto& p = b.items[j];
//             std::cout << "num<" << p.first << ", " << p.second << ">"
//                       << (j + 1 == b.items.size() ? "" : ", ");
//         }
//         std::cout << "]  sum = " << b.sum << '\n';
//     }
//     return 0;
// }
